package leecode

func combinationSum(candidates []int, target int) (result [][]int) {
	var backtracking func(target, startIndex int)
	path := make([]int, 0, len(candidates))
	backtracking = func(target, startIndex int) {
		if target <= 0 {
			if target == 0 {
				temp := make([]int, len(path))
				copy(temp, path)
				result = append(result, temp)
			}
			return
		}
		for i := startIndex; i < len(candidates); i++ {
			target -= candidates[i]
			path = append(path, candidates[i])
			backtracking(target, i)
			target += candidates[i]
			path = path[:len(path)-1]
		}
	}
	backtracking(target, 0)
	return
}
